package com.cat.graphTheory;

import java.util.*;
/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/get-watched-videos-by-your-friends/description/
 * @create 2025/9/19 19:27
 * @since JDK17
 */

public class Solution14 {
    public List<String> watchedVideosByFriends(List<List<String>> watchedVideos, int[][] friends, int id, int level) {
        TreeMap<String, Integer> ans = new TreeMap<>();

        // friends : 其实就是图
        int n = friends.length;
        boolean[] vis = new boolean[n];
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(id);
        vis[id] = true;
        for (int i = 0; i < level; i++) {
            for (int j = 0, end = q.size(); j < end; j++) { // 一次跑一层
                int x = q.poll();
                for (int y : friends[x]) {
                    if (!vis[y]) {
                        vis[y] = true;
                        q.offer(y);
                    }
                }
            }
        }
        while (!q.isEmpty()) {
            List<String> list = watchedVideos.get(q.poll());
            for (var s : list) {    // 收集起他们的频率
                ans.merge(s, 1, Integer::sum);
            }
        }

        List<String> res = new ArrayList<>(ans.keySet());
        Collections.sort(res, (a, b) -> {
            int cnt1 = ans.get(a), cnt2 = ans.get(b);
            if (cnt1 != cnt2) {
                return cnt1 - cnt2;
            } else {
                return a.compareTo(b);
            }
        });

        return res;
    }
}
